#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 定义线索二叉链表结构
typedef struct tbtnode
{
    char data;              // 数据
    struct tbtnode *lchild; // 左子结点
    struct tbtnode *rchild; // 右子结点
    int ltag;               // 左线索标志域 0-lchild 的左孩子 1-lchild 的前趋
    int rtag;               // 右线索标志域 0-rchild 的右孩子 1-rchild 的后趋
} ThrBinNode, *ThrBinTree;

/**
 * 创建二叉树，通过完全二叉树输入层次
 */
ThrBinTree createThrBinTreeByComp()
{
    ThrBinNode *Q[100];
    ThrBinNode *cur;
    ThrBinTree BT = NULL;

    int front = 1, rear = 0;

    printf(">>input char element: ");
    char ch;
    while ((ch = getchar()) != '\n')
    {
        cur = NULL;
        if (ch != '@')
        {
            // 新结点申请、赋值
            cur = (ThrBinTree)malloc(sizeof(ThrBinNode));
            cur->data = ch;
            cur->lchild = cur->rchild = NULL;
        }
        rear++;
        Q[rear] = cur;
        // 为1则说明是根结点
        if (rear == 1)
            BT = cur;
        else
        {
            // 结点不为null 且出队不为null
            if (cur != NULL && Q[front] != NULL)
            {
                // 偶数则新结点为左孩子， 奇数为右孩子
                if (rear % 2 == 0)
                    Q[front]->lchild = cur;
                else
                    Q[front]->rchild = cur;
            }

            // 为奇数，front 指向下一个双亲
            if (rear % 2 != 0)
                front++;
        }
    }

    return BT;
}

/**
 * 二叉树加中序线索
 */
void inorderThread(ThrBinTree tbt)
{
    // 定义指向前趋结点的指针pre 静态变量，保存刚访问过的结点
    static ThrBinNode *pre = NULL;
    // 二叉树为空时结束递归
    if (tbt != NULL)
    {
        // 左子树线索化
        inorderThread(tbt->lchild);
        if (tbt->lchild == NULL)
            tbt->ltag = 1;
        else
            tbt->ltag = 0;

        if (tbt->rchild == NULL)
            tbt->rtag = 1;
        else
            tbt->rtag = 0;

        if (pre)
        {
            if (pre->rtag == 1)
                pre->rchild = tbt; // 给前趋结点加后继线索
            if (pre->ltag == 1)
                pre->lchild = tbt; // 给前趋结点加前趋线索
        }

        // 将刚访问过的当前结点置为前趋结点
        pre = tbt;
        // 右子树线索化
        inorderThread(tbt->rchild);
    }
}

/**
 * 查找某结点*p的后继结点
*/
ThrBinNode *inorderNext(ThrBinNode *p)
{
    // 右线索域，返回中序后的后继结点指针
    if (p->rtag == 1)
        return p->rchild;

    // 从*p的右孩子开始
    p = p->rchild;
    while (p->ltag == 0)
    {
        // 沿左指针链 向下查找
        p = p->lchild;
    }
    return p;
}

/**
 * 线索二叉树的遍历
 */
void tinorderThread(ThrBinTree tbt)
{
    if (tbt == NULL)
        return;
    ThrBinNode *p = tbt;
    while (p->ltag == 0)
    {
        p = p->lchild;
    }

    do
    {
        printf("%c ", p->data);
        p = inorderNext(p);
    } while (p != NULL);
}

int main()
{
    ThrBinTree TBT = createThrBinTreeByComp();
    inorderThread(TBT);
    tinorderThread(TBT);
    printf("\n");
    return 0;
}